class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        if not intervals:
        	return
        intervals.sort(key=lambda a: [a[0], a[1]])
        res = []
        res.append(intervals[0])
        for interval in intervals[1:]:
        	nowbb, nowee = interval
        	if nowbb > res[-1][1]:
        		res.append(interval)
        	else:
        		res[-1][1] = max(nowee, res[-1][1]) 

        return res

    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        for i in range(len(nums) - 2 ):
        	k = nums[i]
        	if k > 0:
        		break
        	if i > 0 and nums[i] == nums[i-1]:
        		continue

        	j = i + 1
        	e = len(nums) - 1
        	while j < e:
        		if k + nums[j] + nums[e] == 0:
        			res.append([nums[i], nums[j], nums[e]])
        			j += 1
        			e -= 1
        			while j < len(nums) - 1 and nums[j] == nums[j - 1]:
        				j += 1
        			while 0 < e and nums[e] == nums[e + 1]:
        				e -= 1
        		elif k + nums[j] + nums[e] > 0:
        			e -= 1
        			while 0 < e and nums[e] == nums[e + 1]:
        				e -= 1
        		else:
        			j += 1
        			while j < len(nums) - 1 and nums[j] == nums[j - 1]:
        				j += 1

       	return res

    def dfs(self, nowi, nowj, now_num):
       
        if 0 <= nowi < self.height and 0 <= nowj < self.width:
            if self.map_flag[nowi][nowj]:
                return 0
            self.map_flag[nowi][nowj] = 1
            if self.grid[nowi][nowj]:
                temp_num = 1
                for direction in self.directions:
                    next_i = nowi + direction[0]
                    next_j = nowj + direction[1]
                    # print self.map_flag[next_i][next_j]
                    # if not self.map_flag[next_i][next_j]:
                    temp_num += self.dfs(next_i, next_j, 0)
                return temp_num
        return 0

    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        res = 0
        if not grid:
        	return res

        height = len(grid)
        if height == 0:
        	return res
        width = len(grid[0])
        
        self.map_flag = []
        self.grid = grid
        for i in range(height):
            temp = []
            for i in range(width):
                temp.append(0)
            self.map_flag.append(temp)
            temp = []   
        self.directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        self.height = height
        self.width = width
        for i in range(height):
        	for j in range(width):
        		if not self.map_flag[i][j]:
        			# print i, j
        			# map_flag[i][j] = 1
        			if grid[i][j]:
        				now_num = 0
        				now_num += self.dfs(i, j, 0)
        				res = max(res, now_num)



        return res


    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return
        k = k % len(nums)
        nums.reverse()
        nums1 = nums[0:k]
        nums1.reverse()
        nums[0:k] = nums1
        nums1 = nums[k:]
        nums1.reverse()
        nums[k:] = nums1

    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0 
        right = len(nums) - 1
        mid = -1
        last = mid
        while(left <= right):
        # def binary_search(left, right):
            if left > right:
                return -1
            mid = left + (right - left) / 2
            leftvalue = nums[left]
            rightvalue = nums[right]
            value = nums[mid]
            # print mid
            if value == target:
                return mid
            print mid
            if leftvalue <= rightvalue:
                if value < target:
                    left = mid + 1
                else:
                    right = mid
            else:
                if value > target:
                    left = mid
                else:
                    if target < rightvalue:
                        left = mid
                    else:
                        left = mid 
        return -1
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        max_rel = -9999999999
        tmp_rel = 0
        for num in nums:
            tmp_rel += num
            max_rel = max(max_rel, tmp_rel)
            if tmp_rel < 0:
                tmp_rel = 0
        return max_rel
        
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        height = len(matrix)
        if not height:
            return 0
        width = len(matrix[0])
        if not width:
            return 0
        flag = [[0] * width for i in range(height)]
        rel = 0
        for i in range(width):
            flag[0][i] = int(matrix[0][i])
            rel = max(rel, flag[0][i])

        for j in range(height):
            flag[j][0] = int(matrix[j][0])
            rel = max(rel, flag[j][0])

        
        for i in range(1, height):
            for j in range(1, width):
                if matrix[i][j] == '1':
                    flag[i][j] = min(flag[i-1][j-1], flag[i-1][j], flag[i][j-1]) + 1
                    rel = max(rel, flag[i][j] * flag[i][j])
                else:
                    flag[i][j] = 0
        return rel

    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if not triangle:
            return 0
        import copy
        rel =[]
        last_rel = []
        for i in range(len(triangle)):
            row = triangle[i]
            if i == 0:
                rel.append(row[0])
                continue
            else:
                rel.append(0)
            last_rel = copy.deepcopy(rel)
            for j in range(len(row)):
                rel[j] = 0xffff
                if j != len(row) - 1:
                    rel[j] = min(last_rel[j] + row[j], rel[j])
                if j != 0:
                    rel[j] = min(last_rel[j - 1] + row[j], rel[j])
        res = min(rel)
        return res

    def maxEnvelopes(self, envelopes):
        res = 0
        if not envelopes:
            return res

        def cmp_fun(a, b):
            if a[0] != b[0]:
                return a[0] - b[0]
            elif a[1] != b[1]:
                return b[1] - a[1]
            else:
                return -1       
        envelopes.sort(cmp=cmp_fun)
        print envelopes
        flag = [-1 for i in range(len(envelopes))]
        last_contain = [-1 for i in range(len(envelopes))]
        for index, envelope in enumerate(envelopes):
            last = last_contain[index]
            flag[index] = 1
            i = index - 1
            while i > last:
            #     pass
            # for i in range(index - 1, last, -1):
                now_env = envelopes[i]
                if envelope[0] > now_env[0] and envelope[1] > now_env[1]:
                    if flag[i] + 1 > flag[index]:
                        flag[index] = flag[i] + 1
                        last_contain[index] = i
                        if last != -1:
                            if last < last_contain[i]:
                                last = last_contain[i]
                        else:
                            last = last_contain[i]
                i -= 1
        res = max(flag)
        return res


    def findLengthOfLCIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = 0
        if not nums:
            return length

        tmp_len = 0
        last_num = -1
        for i in range(len(nums)):
            if tmp_len == 0:
                tmp_len = 1
            else:
                if nums[i] > last_num:
                    tmp_len += 1
                else:
                    tmp_len = 1
                    
            last_num = nums[i]
            length = max(length, tmp_len)

        return length

    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = 0
        nums_set = set(nums)
        for num in nums_set:
            tmp_num = num
            tmp_len = 1
            while True:
                if tmp_num + 1 in nums_set:
                    tmp_num += 1
                    tmp_len += 1
                else:
                    break
            length = max(length, tmp_len)
        return length

    def permutation_bc(self, pos, remain_num, re_nums, rel):
        x_pos = self.n - pos - 1
        if x_pos:
            if remain_num % self.per_num[x_pos] == 0:
                re_pos = remain_num / self.per_num[x_pos] - 1
            else:
                re_pos = remain_num / self.per_num[x_pos]
            
        else:
            re_pos = 0
        rel += str(re_nums[re_pos])
        del re_nums[re_pos]
        if x_pos > 0:
            res = self.permutation_bc(pos + 1, remain_num - re_pos * self.per_num[x_pos], re_nums, rel)
        else:
            self.res = rel

    def getPermutation(self, n, k):
        tmp_num = 1
        self.n = n
        self.per_num = [0]
        for i in range(1, 10):
            tmp_num *= i 
            self.per_num.append(tmp_num)
        print self.per_num
        remain_nums = [i +1 for i in range(n)]
        print remain_nums
        k = k % self.per_num[n]
        self.permutation_bc(0, k , remain_nums, '')
        return self.res

    def get_parent_type(self, index):
        if self.union_parent[index] != index:
            return self.get_parent_type(self.union_parent[index])
        else:
            return self.union_parent[index]

    def union(self, x, y):
        px = self.get_parent_type(x)
        py = self.get_parent_type(y)
        if px != py:
            self.union_parent[px] = py

    def findCircleNum(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        N = len(M)
        self.union_parent = [i for i in range(N)]
        for i in range(N):
            for j in range(i):
                if M[i][j] == 1:
                    self.union(i, j)

        for i in range(N):
            self.union_parent[i] = self.get_parent_type(i)
        print self.union_parent
        rel_set = set(self.union_parent)

        return len(rel_set)

    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        

if __name__ == '__main__':
    ll = [[5,4],[6,4],[6,7],[2,3]]
    nums = [0,1,0,2,1,0,1,3,2,1,2,1]
    aa = Solution()
    print aa.maxEnvelopes(ll)